package com.gxc.array;

import java.util.Arrays;

/**
 * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。
 * 再给定一个正数limit，代表一艘船的载重。以下是坐船规则，
 * 1) 每艘船最多只能做两人;
 * 2)乘客的体重和不能超过limit。
 * 返回如果同时让这N个人过河最少需要几条船。
 *
 * 解法一：
 * 1.数组先排序
 * 2.排序后从数字大的一边开始遍历，最大的数字和最小的数字组合能否坐一船，
 *      如果能，则船数加1，数组减去最大最小值后循环
 *      如果不能，则船数加1，数组减去最大值后循环
 * 解法二：
 * 1.数组先排序
 * 2.数组中找到   小于等于 limit/2  最右的数字，位置标为L，L+1标为R
 *      2.1 L和R位置相加，如果 > limit， 则 R 位置不动， L 左移， L 记为 X 类型的数字
 *      2.2 L和R位置相加，如果 <= limit， 则 R 右移，查看 R 右边有多少数组与 L 相加符合条件
 *          （右边移动几位，左边也移动几位），这类数字记为 Y 类型
 *      2.3 如果 R 位置找不到符合条件的数字，则 L 左移， L 记为 X 类型的数字
 *      2.4 最终左边或右边先到头，如果左边先到头，则右边剩余的数字都为 Z 类型，
 *          如果右边先到头，则右边剩余的数字都为 X 类型，
 *      船的总数等于 Z（单人一船） + X(左部分两人一船) + Y(左部分和右部分两人一船)
 */
public class Ship {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5};
        int limit = 6;
        System.out.println(process(arr, limit));
        System.out.println(process2(arr, limit));
        System.out.println(process3(arr, limit));
    }

    public static int process(int[] arr, int limit) {
        Arrays.sort(arr);

        int min = 0;
        //数组头
        int s = 0 ;
        //数组尾
        int e = arr.length-1;
        while (s <= e) {
            if (arr[e] + arr[s] <= limit) {
                s++;
            } else {
            }
            min++;
            e--;
        }
        return min;
    }

    /**
     * 解法二
     * @param arr
     * @param limit
     * @return
     */
    public static int process2(int[] arr, int limit) {
        Arrays.sort(arr);

        int N = arr.length;
        int half = limit/2;
        //小于等于 limit/2  最右的数字
        int L = -1;
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i]<=half) {
                L = i;
                break;
            }
        }
        //所有数字都大于船载重的一半，都得单独坐船
        if (L == -1) return N;

        int R = L+1;
        int x = 0;
        int y = 0;
        int z = 0;
        while (L>=0 && R< N) {
            if (arr[L] + arr[R] > limit) {
                L--;
                x++;
            } else {
                int r=0;
                while (R+r < N && arr[L] + arr[R+r] <= limit) {
                    r++;
                }
                y = y + r;
                L = L - r;
                R = R + r;
            }
        }
        if (L>0) {
            x = x + L + 1;
        } else if (R < N) {
            z = N - R;
        }

        return x/2 + y + z + (x%2==0?0:1);
    }

    /**
     * https://blog.csdn.net/z1171127310/article/details/128173785
     * @param arr
     * @param limit
     * @return
     */
    public static int process3(int[] arr, int limit) {
        Arrays.sort(arr);

        int N = arr.length;
        int half = limit/2;
        //小于等于 limit/2  最右的数字
        int lessR = -1;
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i]<=half) {
                lessR = i;
                break;
            }
        }
        //所有数字都大于船载重的一半，都得单独坐船
        if (lessR == -1) return N;

        int L = lessR;
        int R = lessR+1;
        //画 X 的数量
        int noUesd = 0;

        while (L >= 0) {
            int solved = 0;
            while (R<N && arr[L] + arr[R] <= limit) {
                R++;
                solved++;
            }
            //R来到不达标的位置
            if (solved == 0) {
                noUesd++;
                L--;
            } else {
                L = Math.max(-1, L - solved);
            }
        }

        int all = lessR + 1;
        int uesd = all - noUesd;
        int moreUnsolved = (N - all) - uesd;
        return uesd + ((noUesd+1) >> 1) + moreUnsolved;
    }

}
